The invention relates to a hard-wired circuit for sorting data.
Large groups of numbers need to be sorted into numerical order in computer graphics and applications employing relational data bases. Sorting is typically accomplished using a general purpose processor and software commands to sort unsorted data stored in a memory. Two common methods are the bubble sort method and the bucket sort method.
The bubble sort method utilizes a compare circuit to find the largest value of the first two memory locations. If the largest value is in the lower memory location, the values are swapped, and the value now in the second location is compared with the one above it, and so on, until the largest value in the memory has been "bubbled up" to the top of the memory array. The procedure is repeated, bringing the second largest value up to the second location, etc. Sorting N items involves N.sup.2 /2 passes through the compare loop. As the number of items to be sorted increases, the number of passes gets so large that it seriously impedes performance.
The bucket sort method uses the actual value of the number to be sorted as its memory address. An advantage to this method is that it is quick. A drawback is the amount of memory required, as there must be as many memory locations (buckets) as possible values, regardless of the number of numbers to be sorted. E.g., sorting a series of 32-bit numbers requires that over four-billion memory locations be made available, even if there are only 100 numbers to sort. Other disadvantages are that pointers are required for duplicate values, and accessing the sorted data is slow, because each memory location must be examined for data.
A high performance integrated circuit for sorting numbers is the Advanced Micro Devices Content Addressable Data Manager, AM95C85. As its name suggests, the memory can be addressed by the values of the numbers stored in memory. Its speed of performance is a function of how well the input data are sorted.